class Solution {
public:
    void _sort(vector<int>& nums, int begin, int end)
    {
        if (begin >= end) return;
        int left = begin - 1, right = end + 1, key = nums[begin], cur = begin;
        while (cur < right)
        {
            if (nums[cur] == key)
            {
                cur++;
            }
            else if (nums[cur] > key)
            {
                right--;
                swap(nums[cur], nums[right]);

            }
            else
            {
                left++;
                swap(nums[left], nums[cur]);
                cur++;
            }
        }
        _sort(nums, begin, left);
        _sort(nums, right, end);


    }

    vector<int> sortArray(vector<int>& nums) {
        _sort(nums, 0, nums.size() - 1);
        return nums;
    }
};